package com.chapter4.graph.sp;

import java.util.Stack;

import com.chapter2.sort.IndexMinPQ;

/**
 * 
 * @ClassName: DijkstraSP
 * @Description: Dijkstra最短路径算法
 * @author minjun
 * @date 2015年3月11日 上午12:34:41
 * 
 */
public class DijkstraSP {

	private final int s;

	// distTo[v]=w表示从s到v的距离为w
	private double[] distTo;

	// edgeTo[v]=w表示从s->v的最后一条边为w
	private DirectEdge[] edgeTo;

	private IndexMinPQ<Double> pq;

	public DijkstraSP(DirectWeightGraph g, int s) {
		this.s = s;
		int len = g.V();
		distTo = new double[len];
		for (int i = 0; i < len; i++) {
			// 初始化所有项为正无穷大
			distTo[i] = Double.POSITIVE_INFINITY;
		}
		edgeTo = new DirectEdge[len];
		// 另：初始化特殊情况
		distTo[s] = 0.0;

		// 用带索引的优先队列存储所有边(之所以用带索引的是因为可能考虑到要修改已有的边)
		pq = new IndexMinPQ<Double>(len);
		pq.insert(s, 0.0);
		// 获取所有点，并放松这些点的相邻边
		while (!pq.isEmpty()) {
			relax(g, pq.delMin());
		}
	}

	/**
	 * 
	 * @Title: relax
	 * @Description: 放松该边
	 * 
	 *               放松某边：获取到该边to(目的地)的最短路径
	 * 
	 * @param @param edge 设定文件
	 * @return void 返回类型
	 * @throws
	 */
	private void relax(DirectWeightGraph g, int i) {
		for (DirectEdge edge : g.adj(i)) {
			int v = edge.from();
			int w = edge.to();
			if (distTo[w] > distTo[v] + edge.weight()) {
				distTo[w] = distTo[v] + edge.weight();
				edgeTo[w] = edge;
				if (pq.contains(w))
					pq.changeKey(w, distTo(w));
				else
					pq.insert(w, distTo(w));
			}
		}
	}

	public double distTo(int v) {
		return distTo[v];
	}

	public boolean hasPathTo(int v) {
		return distTo[v] < Double.POSITIVE_INFINITY;
	}

	public Iterable<DirectEdge> pathTo(int v) {
		Stack<DirectEdge> edges = new Stack<DirectEdge>();
		for (int i = v; i != s; i = edgeTo[i].from()) {
			edges.push(edgeTo[i]);
		}
		return edges;
	}
}
